package com.example.algorithm.dynamicprogramming;

/**
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 *  示例 1：  
 * 输入：matrix = {
 *  {'1','0','1','0','0'},
 *  {'1','0','1','1','1'},
 *  {'1','1','1','1','1'}
 * ,{'1','0','0','1','0'}}
 * 输出：4
 *
 *  示例 2：  
 * 输入：matrix = {{'0','1'},{'1','0'}}
 * 输出：1
 *
 *  示例 3：  
 * 输入：matrix = {{'0'}}
 * 输出：0
 */
public class Leetcode221_MaximalSquare {
    public static void main(String[] args) {
        char[][] matrix;
        matrix = new char[][]{
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}};
//        matrix = new char[][] {{'0'}};
//        matrix = new char[][] {{'0','1'},{'1','0'}};
        System.out.println(new Solution().maximalSquare(matrix));

    }
    
    static class Solution {

        /**
         * 解法二:动态规划
         *
         * 1.原问题与子问题:
         *   求解以(i,j)为右下角的最大的正方形边长
         *
         * 2.设计状态:
         *   dp[i,j]以(i,j)为右下角的最大的正方形边长
         *
         * 3.状态转移方程
         *   以(i,j)为右下角的最大的正方形边长,取决于它的左边(dp[i - 1, j]),上面(dp[i, j - 1]）,以及左上(dp[i - 1, j - 1])的值
         *   if matrix[i,j] = 1 则 dp[i,j] = min(dp[i - 1, j], dp[i - 1, j - 1], dp[i, j - 1]) + 1
         *   if matrix[i,j] = 0 则 dp[i,j] = 0 (不可能组成正方形)
         *
         *   目标值:max(dp[i][j]) * max(dp[i][j])
         *
         * 4.边界值
         *   if matrix[i][0] = 0 dp[i][0] = 0
         *   if matrix[0][j] = 1 dp[0][j] = 1
         * @param matrix
         * @return
         */
        private int maximalSquare2(char[][] matrix) {
            int rows = matrix.length;
            int columns = matrix[0].length;
            int maxSide = 0;
            int[][] dp = new int[rows][columns]; // 以(i,j)为右下角的最大的正方形边长
            // 初始化第一列的值
            for (int i = 0; i < rows; i++) {
                if (matrix[i][0] == '1') {
                    dp[i][0] = 1;
                    maxSide = Math.max(maxSide, dp[i][0]);
                }
            }
           // 初始化第一行的值
            for (int i = 1; i < columns; i++) {
                if (matrix[0][i] == '1') {
                    dp[0][i] = 1;
                    maxSide = Math.max(maxSide, dp[0][i]);
                }
            }

            for (int i = 1; i < rows; i++) {
                for (int j = 1; j < columns; j++) {
                    if (matrix[i][j] == '1') {
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                    } else {
                        dp[i][j] = 0;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }

            return maxSide * maxSide;
        }

        /**
         * 解法一:暴力法
         * 遍历矩阵,遇到'1'的就依次增加一行一列判断该区域是否全是1
         * @param matrix
         * @return
         */
        public int maximalSquare1(char[][] matrix) {
            int rows = matrix.length;
            int columns = matrix[0].length;
            int maxSide = 0;
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (matrix[i][j] == '1') {
                        maxSide = Math.max(maxSide, 1);
                        int possibleMaxSideLen = Math.min(rows - i, columns - j);// 最大能增加的边长

                        for (int k = 1; k < possibleMaxSideLen; k++) { // 依次增加一行一列
                            // 判断新增的一行一列是否均为 1
                            boolean flag = true;
                            if (matrix[i + k][j + k] == '0') break; // 判断增加的一行一列交叉那个元素是否是'1'
                            for (int m = 0; m < k; m++) {
                                if (matrix[i + k][j + m] == '0') { // 对增加的一行进行判断
                                    flag = false;
                                    break;
                                }

                                if (matrix[i + m][j + k] == '0') {// 对增加的一列进行判断
                                    flag = false;
                                    break;
                                }
                            }

                            if (flag) {
                                maxSide = Math.max(maxSide, k + 1);
                            } else {
                                break;
                            }
                        }

                    }
                }
            }

            return maxSide * maxSide;
        }

        public int maximalSquare(char[][] matrix) {
            return maximalSquare2(matrix);
        }

    }
}
